//
//  ProblemMS0804.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/4.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 08.04. 幂集
 幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
 说明：解集不能包含重复的子集。

 示例:
  输入： nums = [1,2,3]
  输出：
 [
   [3],
   [1],
   [2],
   [1,2,3],
   [1,3],
   [2,3],
   [1,2],
   []
 ]
 */
@objcMembers class ProblemMS0804: NSObject {
    func solution() {
        print(subsetsWei([1,2,3]))
    }
    
    /*
     方法一：依次放入结果集中
     遍历数组，每一次遇到一个数，放入已经上一次的结果集中 [1,2,3]
     1: []
     2: i = 0, 结果集里面的每个放入1，[] -> [1], 结果集：[] [1]
     3: i = 1, 结果集里面的每个放入2，[],[1] -> [2], [1,2], 结果集：[] [1] [2] [1,2]
     */
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result:[[Int]] = [[]]
        for num in nums {
            for list in result {
                var nList = list
                nList.append(num)
                result.append(nList)
            }
        }
        return result
    }
    
    /*
     方法二：位运算
     数组中的每一个数字都有选和不选两种状态，我们可以用0和1表示，0表示不选，1表示选择。如果数组的长度是n，那么子集的数量就是2^n。比如数组长度是3，就有8种可能，分别是
     转换成二进制 -> 十进制
     [0，0，0] ->  0
     [0，0，1] ->  1
     [0，1，0] ->  2
     [0，1，1] ->  3
     [1，0，0] ->  4
     [1，0，1] ->  5
     [1，1，0] ->  6
     [1，1，1] ->  7
     他的总数就是 2的nums.count次方
     */
    func subsetsWei(_ nums: [Int]) -> [[Int]] {
        var result:[[Int]] = []
        let len = 1 << nums.count
        for sn in 0..<len {
            // 将10进制转换成二进制的数组
            var list:[Int] = []
            for (j, num) in nums.enumerated() {
                if sn >> j & 1 == 1 {
                    list.append(num)
                }
            }
            result.append(list)
        }
        return result
    }
}
